package com.easy.leetcode.dp;

/**
 * @ClassName LastStoneWeightII1049
 * @Description 1049. 最后一块石头的重量 II
 * 提示：
 * 1 <= stones.length <= 30
 * 1 <= stones[i] <= 100
 * @Author zheng
 * @Date 2021/10/11 17:35
 * @Version 1.0
 **/
public class LastStoneWeightII1049 {
    /**
     * @return int
     * @Description
     * @Date 2021/10/11 17:38
     * @Param [stones]
     **/
    public int lastStoneWeightII(int[] stones) {
        int sum = 0;
        for (int stone : stones) {
            sum += stone;
        }
        int target = sum / 2;
        //容量为j的背包能背的最大重量
        int[] dp = new int[15001];
        for (int stone : stones) {
            for (int j = target; j >= stone; j--) {
                dp[j] = Math.max(dp[j], dp[j - stone] + stone);
            }
        }
        return sum - dp[target] * 2;
    }
}
